/*
    1️⃣ 用前缀和表示任意区间和，最大子数组和等于“当前前缀和减去历史最小前缀和”。
    2️⃣ 遍历过程中不断更新前缀和，并维护前缀和的最小值，从而动态求得最大差值。

    简洁表达这个策略就是：
    “最大收益 = 当前累积 - 历史最差”，
    就像炒股低买高卖的思想。📈
*/

// #include <limits.h>  // 提供 INT_MIN 等整型边界值

// step 1# 定义两个辅助宏：计算最大值和最小值
#define MAX(a, b) ((b) > (a) ? (b) : (a))  // 求较大值
#define MIN(a, b) ((b) < (a) ? (b) : (a))  // 求较小值

// step 2# 求解最大子数组和（前缀和思想）
int maxSubArray(int* nums, int numsSize) {
    // step 3# 初始化答案为最小整数
    int ans = INT_MIN;           // 当前最大子数组和
    int min_pre_sum = 0;         // 当前遇到的最小前缀和（初始为0）
    int pre_sum = 0;             // 当前前缀和

    // step 4# 遍历数组，更新前缀和及最大子数组和
    for (int i = 0; i < numsSize; i++) {
        pre_sum += nums[i];                                     // 更新当前前缀和
        ans = MAX(ans, pre_sum - min_pre_sum);                  // 当前最大子数组和为 pre_sum 减去之前最小前缀和
        min_pre_sum = MIN(min_pre_sum, pre_sum);                // 更新最小前缀和
    }

    // step 5# 返回结果
    return ans;
}
